package leetcode.list_problem;

/**
 * 面试题 02.04. 分割链表
 * https://leetcode-cn.com/problems/partition-list-lcci/
 */
public class SplitList {
    public ListNode partition(ListNode head, int x) {
        ListNode smallNode = new ListNode();
        ListNode bigNode = new ListNode();
        ListNode smallHead = smallNode;
        ListNode bigHead = bigNode;
        while (head != null){
            if (head.val < x){
                smallHead.next = head;
                smallHead = smallHead.next;
            }else {
                bigHead.next = head;
                bigHead = bigHead.next;
            }
            head = head.next;
        }
        smallHead.next = bigNode.next;
        bigHead.next = null;
        return smallNode.next;
    }
}
